package com.tjetc._1collection._2set;

import java.util.HashSet;
import java.util.Set;

@SuppressWarnings("all")
public class _2HashSetDetail {
    public static void main(String[] args) {
        /*
            HashSet:
            1.HashSet实际上是HashMap
            2.可以存放null值，但是只能有⼀个null
            3.HashSet不保证元素是有序的

            底层：
            1.HashSet是如何做到去重处理？源码分析
            2.HashSet底层是HashMap,HashMap底层是(数组+链表+红⿊树【不讲 二叉树 平衡二叉树 红黑树】)

            结论：
            1. HashSet底层是HashMap
            2. 添加一个元素时，先得到该元素的hash值----->变成数组的索引值
            3. 找到存储数据表table，看这个索引位置是否已经有存放的元素
              a. 如果没有，直接加入
              b. 如果有，调用 equals 比较（由程序员控制），如果相同，就放弃添加，如果不相同，则添加到最后
            4. 在Java8中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)。
         */

        /*
            ------------------------HashSet底层是HashMap---------------
            维护了一个HashMap
            private transient HashMap<E,Object> map;


            ------------------------演示首次添加和去重原理---------------------------
            1.第二次添加
            public boolean add(E e) {
                调用的是map的put方法
                PRESENT： 这个参数是map中的value 由于set只有一个值 所以在这里new Object当做占位符
                return map.put(e, PRESENT)==null;
            }

            2.调用了map的put
            key：传进来的元素
            public V put(K key, V value) {
                调用真正添加值的方法
                hash(key)： 自己有一个计算hash值的算法

                return putVal(hash(key), key, value, false, true);
            }


            3. putVal方法
            参数：
                onlyIfAbsent：默认传递的是false 修改原有存在的值
                evict：这个参数在HashMap中是为了给LinkedHashMap用的 我们暂时不用关心
            final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                创建一些临时变量 用来保存数据
                Node<K,V>[] tab; Node<K,V> p; int n, i;

                table：HashMap$Node类型的数组 16个长度
                    判断当前的数组是否为null
                    判断当前数组的长度是否为0
                    结果的为false
                if ((tab = table) == null || (n = tab.length) == 0) {
                    进行第一次扩容
                    n = (tab = resize()).length;
                }
                i = 当前长度-1 和 当前的hash 做与位运算的结果 （表示在节点数组的索引）
                    ---------------
                    首次添加的位置
                    ---------------
                p来接收i索引位置上的元素值
                判断p的值是否为null
                目的是先能确定要插入的元素应该在数组中的某一个位置
                if ((p = tab[i = (n - 1) & hash]) == null) {
                    如果为null 直接创建新节点并把新节点放在数组中作为链表的第一个节点
                    tab[i] = newNode(hash, key, value, null);
                }
                else {
                    ----------
                    首次去重
                    -------------
                    定义了一些辅助变量
                    Node<K,V> e; K k;
                        判断存在元素的hash值和传进元素的hash值进行比较
                            k = 原有元素的k 和 传进元素的key 进行比较
                                传进的key是否为null
                                传进的key和原有的key通过equals方法比较
                    注意：这个判断就是去重的核心 调用了hash和equal方法
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        将原有的数据进行保存
                        e = p;
                    判断当前你放进的节点类型是不是树节点
                    else if (p instanceof TreeNode)
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else {
                        ----------------------
                        链表的首次赋值以及链表去重
                        ----------------------
                        无限循环
                        for (int binCount = 0; ; ++binCount) {
                            p是根据hash计算得到的数组的原来的元素 判断后一个是否为null
                            if ((e = p.next) == null) {
                                直接创建一个新节点放在p的后面
                                p.next = newNode(hash, key, value, null);
                                判断当前是否满足树化的条件
                                TREEIFY_THRESHOLD： 链表的个数
                                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            去重核心
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            p = e;
                        }
                    }
                    判断原来存在的元素是否为null元素
                    if (e != null) {
                        如果修改就是替换 如果新增就是复制
                        将数组中原有的元素进行替换
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                       这个方法是JDK留给LinkedHashMap实现的 回调 不用关心
                        afterNodeAccess(e);
                        // 将老值返回
                        return oldValue;
                    }
                }
                ++modCount;
                判断当前的个数是否大于扩容门槛
                if (++size > threshold) {
                    // 执行扩容
                    resize();
                }
                这个方法是JDK留给LinkedHashMap实现的
                afterNodeInsertion(evict);
                return null;
            }




         */

        /*
         --------------------------------扩容机制------------------
            总共有
            1.首次添加的扩容刚开始是一个空数组
            2.链表的长度达到8 数组的扩容机制
            3.当满足扩容门槛的时候 如何扩容
            4.链表的长度达到8 并且数组的长度达到64 如何进行树化（树化的具体实现不讲）

            -------------------------------首次扩容-----------------------
            1.创建HashSet
            public HashMap() {
                loadFactor： 加载因子用来计算扩容门槛
                    初始时是0.75
                this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
            }
            2.首次为HashMap进行扩容
            if ((tab = table) == null || (n = tab.length) == 0){
                n = (tab = resize()).length;
            }
            3. 真正执行扩容的地方
            final Node<K,V>[] resize() {
                拿到老的数组
                Node<K,V>[] oldTab = table;
                初始时为null 直接给0
                int oldCap = (oldTab == null) ? 0 : oldTab.length;
                老的扩容门槛
                int oldThr = threshold;
                创建两个变量
                newCap： 新的容量
                newThr： 新的扩容门槛
                int newCap, newThr = 0;
                if (oldCap > 0) {
                    if (oldCap >= MAXIMUM_CAPACITY) {
                        threshold = Integer.MAX_VALUE;
                        return oldTab;
                    }
                    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                             oldCap >= DEFAULT_INITIAL_CAPACITY)
                        newThr = oldThr << 1;
                }
                else if (oldThr > 0)
                    newCap = oldThr;
                else {
                    计算新的容量
                    DEFAULT_INITIAL_CAPACITY：默认的初始容量为16
                    newCap = DEFAULT_INITIAL_CAPACITY;
                    计算新的扩容门槛：
                        加载因子 * 默认初始容量 = 16 * 0.75 = 12
                    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
                }
                if (newThr == 0) {
                    float ft = (float)newCap * loadFactor;
                    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                              (int)ft : Integer.MAX_VALUE);
                }
                成员属性得到新的扩容门槛
                threshold = newThr;
                @SuppressWarnings({"rawtypes","unchecked"})
                创建数组
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
                table = newTab;

                if (oldTab != null) {
                    for (int j = 0; j < oldCap; ++j) {
                        Node<K,V> e;
                        if ((e = oldTab[j]) != null) {
                            oldTab[j] = null;
                            if (e.next == null)
                                newTab[e.hash & (newCap - 1)] = e;
                            else if (e instanceof TreeNode)
                                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                            else { // preserve order
                                Node<K,V> loHead = null, loTail = null;
                                Node<K,V> hiHead = null, hiTail = null;
                                Node<K,V> next;
                                do {
                                    next = e.next;
                                    if ((e.hash & oldCap) == 0) {
                                        if (loTail == null)
                                            loHead = e;
                                        else
                                            loTail.next = e;
                                        loTail = e;
                                    }
                                    else {
                                        if (hiTail == null)
                                            hiHead = e;
                                        else
                                            hiTail.next = e;
                                        hiTail = e;
                                    }
                                } while ((e = next) != null);
                                if (loTail != null) {
                                    loTail.next = null;
                                    newTab[j] = loHead;
                                }
                                if (hiTail != null) {
                                    hiTail.next = null;
                                    newTab[j + oldCap] = hiHead;
                                }
                            }
                        }
                    }
                }
                return newTab;
            }
            ---------------------------链表的长度达到8 数组的扩容机制--------------------
            1.判断是否树化
            final void treeifyBin(Node<K,V>[] tab, int hash) {
                定义了一些临时变量
                int n, index; Node<K,V> e;
                核心：
                    tab： 当前的数组
                    n： 当前数组的长度是否满足树化的最小容量
                    MIN_TREEIFY_CAPACITY： 64
                if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                    如果达不到树化的标准就进行数组的扩容
                    resize();
                else if ((e = tab[index = (n - 1) & hash]) != null) {
                    TreeNode<K,V> hd = null, tl = null;
                    do {
                        TreeNode<K,V> p = replacementTreeNode(e, null);
                        if (tl == null)
                            hd = p;
                        else {
                            p.prev = tl;
                            tl.next = p;
                        }
                        tl = p;
                    } while ((e = e.next) != null);
                    if ((tab[index] = hd) != null)
                        hd.treeify(tab);
                }
            }

            2. 进行数组的扩容
            final Node<K,V>[] resize() {
                Node<K,V>[] oldTab = table;
                int oldCap = (oldTab == null) ? 0 : oldTab.length;
                int oldThr = threshold;
                int newCap, newThr = 0;
                如果老容量大于0
                if (oldCap > 0) {
                    判断老容量是否大于最大容量
                    if (oldCap >= MAXIMUM_CAPACITY) {
                        扩容门槛复制整数最大值
                        threshold = Integer.MAX_VALUE;
                        返回数组
                        return oldTab;
                    }
                    将数组的容量扩大2倍小于最大容量 并且老容量大于等于默认容量

                    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                             oldCap >= DEFAULT_INITIAL_CAPACITY)
                        计算新的扩容门槛 为原来的2倍
                        newThr = oldThr << 1; // double threshold
                }
                else if (oldThr > 0) // initial capacity was placed in threshold
                    newCap = oldThr;
                else {               // zero initial threshold signifies using defaults
                    newCap = DEFAULT_INITIAL_CAPACITY;
                    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
                }
                if (newThr == 0) {
                    float ft = (float)newCap * loadFactor;
                    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                              (int)ft : Integer.MAX_VALUE);
                }
                threshold = newThr;
                @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
                table = newTab;
                由于原数组中的数据需要挪动到新数组中需要执行下列操作（自行Debug）
                if (oldTab != null) {
                    for (int j = 0; j < oldCap; ++j) {
                        Node<K,V> e;
                        if ((e = oldTab[j]) != null) {
                            oldTab[j] = null;
                            if (e.next == null)
                                这里面有重hash的过程
                                newTab[e.hash & (newCap - 1)] = e;
                            else if (e instanceof TreeNode)
                                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                            else { // preserve order
                                Node<K,V> loHead = null, loTail = null;
                                Node<K,V> hiHead = null, hiTail = null;
                                Node<K,V> next;
                                do {
                                    next = e.next;
                                    if ((e.hash & oldCap) == 0) {
                                        if (loTail == null)
                                            loHead = e;
                                        else
                                            loTail.next = e;
                                        loTail = e;
                                    }
                                    else {
                                        if (hiTail == null)
                                            hiHead = e;
                                        else
                                            hiTail.next = e;
                                        hiTail = e;
                                    }
                                } while ((e = next) != null);
                                if (loTail != null) {
                                    loTail.next = null;
                                    newTab[j] = loHead;
                                }
                                if (hiTail != null) {
                                    hiTail.next = null;
                                    newTab[j + oldCap] = hiHead;
                                }
                            }
                        }
                    }
                }
                return newTab;
            }
            ---------------------------达到扩容门槛 数组的扩容机制--------------------
            1.达到扩容门槛
                判断当前的个数是否大于扩容门槛
                if (++size > threshold) {
                    // 执行扩容
                    resize();
                }
            2.执行扩容
                底层实际上和达到树化条件时的数组扩容一致

            ---------------------------链表的长度达到8并且数组的长度达到64--------------------
            final void treeifyBin(Node<K,V>[] tab, int hash) {
                int n, index; Node<K,V> e;
                if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                    resize();
                先确定数组中哪个位置的链表进行树化
                else if ((e = tab[index = (n - 1) & hash]) != null) {
                    TreeNode<K,V> hd = null, tl = null;
                    将链表中的数据全部转换成树节点
                    do {
                        TreeNode<K,V> p = replacementTreeNode(e, null);
                        if (tl == null)
                            hd = p;
                        else {
                            p.prev = tl;
                            tl.next = p;
                        }
                        tl = p;
                    } while ((e = e.next) != null);
                    if ((tab[index] = hd) != null)
                        执行树化
                        hd.treeify(tab);
                }
            }
            3.开始树化
            final void treeify(Node<K,V>[] tab) {......}

            --------------------------总结-------------------------
            1. HashSet底层是HashMap,第⼀次添加时，table 数组扩容到 16，临界值(threshold)是 16*加
            载因⼦(loadFactor)是0.75 = 12
            2. 如果table 数组使⽤到了临界值 12,就会扩容到 16*2=32,新的临界值就是32*0.75=24,依次类
            推
            3. 在Java8中,如果⼀条链表的元素个数到达 TREEIFY THRESHOLD(默认是 8 ),并且table的⼤
            ⼩ >=MIN_TREEIFY_CAPACITY(默认64),就会进⾏树化(红⿊树)，否则仍然采⽤数组扩容机制。
         */

        /*
            // 演示去重现象
            Set set = new HashSet();
            System.out.println(set.add(1)); // true

            System.out.println(set.add(1)); // 返回了 重复的值 所以判断null时 返回了false
            System.out.println(set); // 只有1

            set.add(new String("abc"));
            set.add(new String("abc"));
            System.out.println(set); // abc

            set.add(new A());
            set.add(new A());
            set.add(new A());
            System.out.println(set);// 俩都存了

         */
        /*
        // 演示首次添加
        Set set = new HashSet();
        set.add(1);

        // 演示首次去重
        set.add(1);

        // 演示创建A对象演示链表首次添加
        set.add(new A());
        set.add(new A());
        // 演示链表去重
        set.add(new A());

        // 演示首次扩容
        Set set1 = new HashSet();
        set1.add(1);

        // 演示链表的长度首次达到8
        Set set2 = new HashSet();
        for (int i = 0; i < 8; i++) {
            set2.add(new A());
        }
        set2.add(new A());

        // 演示达到扩容门槛
        Set set3 = new HashSet();
        for (int i = 0; i < 8; i++) {
            set3.add(new A());
        }
        // 第一次扩容门槛是12个
        for (int i = 0; i < 4; i++) {
            set3.add(new B());
        }
        set3.add(new B());
        */
        // 演示触发树化的过程
        Set set4 = new HashSet(64);
        // 触发一次树化判断
        for (int i = 0; i < 8; i++) {
            set4.add(new A());
        }
        set4.add(new A());
    }
}

class A {
    // 目的是让他们能落到同一个数组的位置
    @Override
    public int hashCode() {
        return 100;
    }
    // 我们没有重写equals方法：他们虽然落在了同一个位置上但是不想等 就意味着他们可以放进去
}

class B {
    @Override
    public int hashCode() {
        return 200;
    }
}
